import java.util.Arrays;
import java.util.Comparator;

/**
 * 435. 无重叠区间
 * https://leetcode-cn.com/problems/non-overlapping-intervals/
 */
public class Solutions_435 {
    public static void main(String[] args) {
//        int[][] nums = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};  // output: 1
//        解释: 移除 {1, 3} 后，剩下的区间没有重叠。

        int[][] nums = {{1, 2}, {1, 2}, {1, 2}};  // output: 2
//        解释: 你需要移除两个 {1, 2} 来使剩下的区间没有重叠。

//        int[][] nums = {{1, 2}, {2, 3}};  // output: 0

        int result = eraseOverlapIntervals(nums);
        System.out.println(result);
    }

    /**
     * 解题思路：贪心算法
     * 要使移除的区间数量最少，那么就要使每个区间都尽可能的小
     */
    public static int eraseOverlapIntervals(int[][] intervals) {
        if (intervals == null || intervals.length <= 1) {
            // 只有一个区间的情况，不会重叠
            return 0;
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // 排序规则：按照结束索引升序排列
                return o1[1] - o2[1];
            }
        });
        int res = 0, end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < end) {
                // 开始索引小于记录的结束索引，说明当前区间与前一区间重叠，那么移除当前区间
                // 重叠的情况中，为什么保留前一区间而不是当前区间？
                // 因为前一区间的 end 一定小于等于当前区间的 end
                res ++;
                continue;
            }
            // 更新结束索引
            end = intervals[i][1];
        }
        return res;
    }
}
